package server.simple100;


import org.junit.Test;

import java.util.ArrayList;


/**
 * [136]只出现一次的数字
 */
public class LeetCode136 {

    @Test
    public void test() {
        int[] nums = {2, 1, 4, 1, 2};
        System.out.println(singleNumber(nums));
    }
    /**
     * 解题思路
     * <p>
     * 类似于摸猪游戏
     * 如果有相同的数被一个人 拿到了，那就把这2个牌放一边， 以此类推，最后剩下的肯定是那个单数的牌
     * </P>
     *
     * @param nums
     * @return int
     * @author wangsong
     * @date 2022/4/7 11:27
     */
    public int singleNumber(int[] nums) {
        ArrayList<Integer> list = new ArrayList();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        while (list.size() > 1) {
            for (int i = 0; i < list.size(); i++) {
                boolean isBack = false;
                for (int j = i + 1; j < list.size(); j++) {
                    if (list.get(i).equals(list.get(j))) {
                        list.remove(j);
                        list.remove(i);
                        isBack = true;
                        break;
                    }
                }
                if (isBack) {
                    break;
                } else {
                    return list.get(i);
                }
            }
        }
        return list.get(0);
    }


    /**
     * 思路1 暴力找
     */
//    public int singleNumber(int[] nums) {
//        for (int i = 0; i < nums.length; i++) {
//            // 判断是否有相等
//            boolean isEqual = false;
//            for (int j = 0; j < nums.length; j++) {
//                if (i != j && nums[i] == nums[j]) {
//                    isEqual = true;
//                    break;
//                }
//            }
//            if (!isEqual) {
//                return nums[i];
//            }
//        }
//        return 0;
//    }



    /**
     *  解法3 计数器
     * @param nums
     * @return
     */
//    public int singleNumber(int[] nums) {
//        int[][] keyNums = new int[999][2];
//        for (int i = 0; i < nums.length; i++) {
//            keyNums[nums[i]][0] = nums[i];
//            keyNums[nums[i]][1] = keyNums[nums[i]][1] + 1;
//        }
//        for (int i = 0; i < keyNums.length; i++) {
//            if (keyNums[i][1] == 1) {
//                return keyNums[i][0];
//            }
//        }
//        return 0;
//    }

}
